package org.example;

import java.util.Arrays;

/*
动态规划五部曲
1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定递归的顺序
5. 举例推导dp数组
*/
public class DynamicProgram {
    // 509. 斐波那契数
    static class Fib {
        public int fib(int n) {
            if (n < 2) {
                return n;
            }
            int a = 0;
            int b = 1;
            int sum = 0;
            for (int i = 1; i < n; i++) {
                sum = a + b;
                a = b;
                b = sum;
            }
            return sum;
        }

        // 非压缩状态的版本
        // 按照上述的动态规划五部曲
        // 1. 确定dp数组以及下标的含义
        // dp[i]的定义为：第i个数的斐波那契数值是dp[i]
        // 2. 确定递推公式
        // 因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
        // 3. dp数组如何初始化
        // 题目中把如何初始化也直接给我们了，如下：dp[0] = 0; dp[1] = 1;
        // 4. 确定遍历顺序
        // 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
        // 5. 举例推导dp数组
        // 按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
        public int fib1(int n) {
            if (n <= 1) {
                return n;
            }
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for (int index = 2; index <= n; index++) {
                dp[index] = dp[index - 1] + dp[index - 2];
            }
            return dp[n];
        }
    }

    // 70. 爬楼梯
    static class ClimbStairs {
        public int climbStairs(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            return dp[n];
        }
    }

    // 746. 使用最小花费爬楼梯
    // 1. 确定dp数组以及下标的含义
    // dp[i]的含义：到达第i台阶所花费的最少体力为dp[i]
    // 2. 确定递推公式
    // 可以有两种途径得到dp[i]，一个是dp[i-1]，一个是dp[i-2]
    // dp[i-1]跳到dp[i]需要花费dp[i-1]+cost[i-1]
    // dp[i-2]跳到dp[i]需要花费dp[i-2]+cost[i-2]
    // 那么究竟是选从dp[i-1]跳还是从dp[i-2]跳呢？
    // 一定是选最小的，所以dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
    // 3. dp数组如何初始化
    // 看一下递归公式，dp[i]由dp[i-1]，dp[i-2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就够了，其他的最终都是dp[0]dp[1]推出
    // 4. 确定遍历顺序
    // 因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
    // 5. 举例推导dp数组
    static class MinCostClimbingStairs {
        // 方式一：第一步不支付费用
        public int minCostClimbingStairs(int[] cost) {
            int len = cost.length;
            int[] dp = new int[len + 1];
            dp[0] = 0;
            dp[1] = 0;
            // 计算到达每一层台阶的最小费用
            for (int i = 2; i <= len; i++) {
                dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
            }
            return dp[len];
        }

        // 方式二：第一步支付费用
        public int minCostClimbingStairs1(int[] cost) {
            int[] dp = new int[cost.length];
            dp[0] = cost[0];
            dp[1] = cost[1];
            for (int i = 2; i < cost.length; i++) {
                dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
            }
            // 最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
            return Math.min(dp[cost.length - 1], dp[cost.length - 2]);
        }

        // 状态压缩，使用三个变量来代替数组
        public int minCostClimbingStairs2(int[] cost) {
            // 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。
            int beforeTwoCost = 0, beforeOneCost = 0, currentCost = 0;
            // 前两个台阶不需要费用就能上到，因此从下标2开始；因为最后一个台阶需要跨越，所以需要遍历到cost.length
            for (int i = 2; i <= cost.length; i++) {
                // 此处遍历的是cost[i - 1]，不会越界
                currentCost = Math.min(beforeOneCost + cost[i - 1], beforeTwoCost + cost[i - 2]);
                beforeTwoCost = beforeOneCost;
                beforeOneCost = currentCost;
            }
            return currentCost;
        }
    }

    // 62. 不同路径
    // 机器人从(0 , 0) 位置出发，到(m - 1, n - 1)终点。
    // 按照动规五部曲来分析：
    // 1. 确定dp数组（dp table）以及下标的含义
    // dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
    // 2. 确定递推公式
    // 题目说：机器人每次只能向下或者向右移动一步
    // 想要求dp[i][j]，只能有两个方向来推导出来，即dp[i - 1][j] 和 dp[i][j - 1]。
    // 此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。
    // 那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。
    // 3. dp数组的初始化
    // 如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
    // 所以初始化代码为：
    // for (int i = 0; i < m; i++) dp[i][0] = 1;
    // for (int j = 0; j < n; j++) dp[0][j] = 1;
    // 4. 确定遍历顺序
    // 这里要看一下递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。
    // 这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。
    // 5. 举例推导dp数组
    static class UniquePaths {
        public static int uniquePaths(int m, int n) {
            int[][] dp = new int[m][n];
            // 行初始化
            for (int i = 0; i < m; i++) {
                dp[i][0] = 1;
            }
            // 列初始化
            for (int j = 0; j < n; j++) {
                dp[0][j] = 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m - 1][n - 1];
        }

        // 状态压缩
        public static int uniquePaths1(int m, int n) {
            // 在二位dp数组中，当前值的计算只依赖正上方和正左方，因此可以压缩成一维数组
            int[] dp = new int[n];
            // 初始化，第一行只能从正左方跳出来，所以只有一条路径
            Arrays.fill(dp, 1);
            for (int i = 1; i < m; i++) {
                // 第一列也只有一条路，不用迭代，所以从第二列开始
                for (int j = 1; j < n; j++) {
                    dp[j] += dp[j - 1]; // dp[j] = dp[j](正上方)+dp[j-1](正左方)
                }
            }
            return dp[n - 1];
        }
    }

    // 63. 不同路径II
    // 62.不同路径 (opens new window)中我们已经详细分析了没有障碍的情况，有障碍的话，其实就是标记对应的dp table（dp数组）保持初始值(0)就可以了。
    // 动规五部曲：
    // 1. 确定dp数组（dp table）以及下标的含义
    // dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
    // 2. 确定递推公式
    // 递推公式和62.不同路径一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
    // 但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）。
    // if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
    //    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    //}
    // 3. dp数组如何初始化
    // 在62.不同路径 (opens new window)不同路径中我们给出如下的初始化：
    // vector<vector<int>> dp(m, vector<int>(n, 0)); // 初始值为0
    // for (int i = 0; i < m; i++) dp[i][0] = 1;
    // for (int j = 0; j < n; j++) dp[0][j] = 1;
    // 因为从(0, 0)的位置到(i, 0)的路径只有一条，所以dp[i][0]一定为1，dp[0][j]也同理。
    // 但如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0。
    // vector<vector<int>> dp(m, vector<int>(n, 0));
    // for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
    // for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
    // 注意代码里for循环的终止条件，一旦遇到obstacleGrid[i][0] == 1的情况就停止dp[i][0]的赋值1的操作，dp[0][j]同理
    // 4. 确定遍历顺序
    // 从递归公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 中可以看出，一定是从左到右一层一层遍历，这样保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值。
    // for (int i = 1; i < m; i++) {
    //    for (int j = 1; j < n; j++) {
    //        if (obstacleGrid[i][j] == 1) continue;
    //        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    //    }
    //}
    static class UniquePathsWithObstacles {
        public int uniquePathsWithObstacles(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[][] dp = new int[m][n];
            // 如果在起点或终点出现障碍，直接返回
            if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
                return 0;
            }
            // 首行初始化，遇到obstacleGrid[i][0] = 1,停止
            for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
                dp[i][0] = 1;
            }
            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
                dp[0][j] = 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[i][j] = obstacleGrid[i][j] == 0 ? dp[i - 1][j] + dp[i][j - 1] : 0;
                }
            }
            return dp[m - 1][n - 1];
        }

        public int uniquePathsWithObstacles1(int[][] obstacleGrid) {
            int m = obstacleGrid.length;
            int n = obstacleGrid[0].length;
            int[] dp = new int[n];

            for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
                dp[j] = 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (obstacleGrid[i][j] == 1) {
                        dp[j] = 0;
                    } else if (j != 0) {
                        dp[j] += dp[j - 1];
                    }
                }
            }
            return dp[n - 1];
        }
    }

    // 343. 整数拆分
    // 动态规划五部曲
    // 1. 确定dp数组（dp table）以及下标的含义
    // dp[i]：拆分数字i，可以得到最大乘积为dp[i].
    // dp[i]的定义将贯彻整个解题过程，下面哪一步想不懂，就想想dp[i]究竟表示的是什么！
    // 2. 确定递推公式
    // 可以想dp[i]最大乘积是怎么得到的呢？
    // 其实可以从1遍历j，然后有两种渠道得到dp[i]
    // 一个是j * (i - j) 直接相乘。
    // 一个是j * dp[i - j]，相当于是拆分(i - j)，对这个拆分不理解的话，可以回想dp数组的定义。
    // 递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    // 也可以这么理解，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。
    // 3. dp的初始化
    // 不少同学应该疑惑，dp[0] dp[1]应该初始化多少呢？
    // 有的题解里会给出dp[0] = 1，dp[1] = 1的初始化，但解释比较牵强，主要还是因为这么初始化可以把题目过了。
    // 严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
    // 拆分0和拆分1的最大乘积是多少？
    // 这是无解的。
    // 这里我只初始化dp[2] = 1，从dp[i]的定义来说，拆分数字2，得到的最大乘积是1，这个没有任何异议！
    // 4. 确定遍历顺序
    // 确定遍历顺序，先来看看递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    // dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。
    // 所以遍历顺序为：
    // for (int i = 3; i <= n ; i++) {
    //    for (int j = 1; j < i - 1; j++) {
    //        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    //    }
    //}
    // 注意 枚举j的时候，是从1开始的。从0开始的话，那么让拆分一个数拆个0，求最大乘积就没有意义了。
    // j的结束条件是 j < i - 1 ，其实 j < i 也是可以的，不过可以节省一步，例如让j = i - 1，的话，其实在 j = 1的时候，这一步就已经拆出来了，重复计算，所以 j < i - 1
    // 至于 i是从3开始，这样dp[i - j]就是dp[2]正好可以通过我们初始化的数值求出来。
    // 更优化一步，可以这样：
    // for (int i = 3; i <= n ; i++) {
    //    for (int j = 1; j <= i / 2; j++) {
    //        dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
    //    }
    //}
    // 因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。
    // 例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。
    // 只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。
    // 那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。
    // 至于 “拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的” 这个我就不去做数学证明了，感兴趣的同学，可以自己证明。
    // 5. 举例推导dp数组
    // 举例当n为10 的时候，dp数组里的数值，如下：
    static class IntegerBreak {
        // dp[i]为正整数i拆分后的结果的最大乘积
        public int integerBreak(int n) {
            int[] dp = new int[n + 1];
            dp[0] = 0;
            dp[1] = 0;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                for (int j = 1; j <= i - j; j++) {
                    // 这里的 j 其实最大值为 i-j,再大只不过是重复而已，
                    //并且，在本题中，我们分析 dp[0], dp[1]都是无意义的，
                    //j 最大到 i-j,就不会用到 dp[0]与dp[1]
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
                    // j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j ，再相乘
                    //而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。
                }
            }
            return dp[n];
        }
    }

    // 96. 不同的二叉搜索树
    static class NumTrees {
        //1. 确定dp数组（dp table）以及下标的含义
        //dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。
        //也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。
        //以下分析如果想不清楚，就来回想一下dp[i]的定义
        //2. 确定递推公式
        //在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
        //j相当于是头结点的元素，从1遍历到i为止。
        //所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
        //3. dp数组如何初始化
        //初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
        //那么dp[0]应该是多少呢？
        //从定义上来讲，空节点也是一棵二叉树，也是一棵二叉搜索树，这是可以说得通的。
        //从递归公式上来讲，dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
        //所以初始化dp[0] = 1
        //4. 确定遍历顺序
        //首先一定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。
        //那么遍历i里面每一个数作为头结点的状态，用j来遍历。
        //5. 举例推导dp数组
        public int numTrees(int n) {
            // 初始化dp数组
            int[] dp = new int[n + 1];
            dp[0] = 1;
            dp[1] = 1;
            for (int i = 2; i <= n; i++) {
                for (int j = 1; j <= i; j++) {
                    dp[i] += dp[j - 1] * dp[i - j];
                }
            }
            return dp[n];
        }
    }

    static class KnapsackProblem {
        // 01 背包
        //有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
        // 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
        // labuladong
        public int knapsack(int[] weight, int[] value, int N, int W) {
            int[][] dp = new int[N][W + 1];
            // 初始化操作
            for (int i = 0; i < N; i++) {
                dp[i][0] = 0;
            }
            for (int j = 1; j <= W; j++) {
                if (j - weight[j] > 0) {
                    dp[0][j] = value[0];
                } else {

                }
            }

            // 遍历
            for (int i = 1; i < N; i++) {
                for (int j = 0; j <= W; j++) {
                    if (j - weight[i - 1] < 0) {
                        // 在这种情况下只能选择不装入背包
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                    }
                }
            }
            return dp[N - 1][W];
        }

        public static void main(String[] args) {
            int N = 3;
            int W = 4;
            int[] weight = {2, 1, 3};
            int[] value = {4, 2, 3};
            int knapsack = new KnapsackProblem().knapsack(weight, value, N, W);
            System.out.println(knapsack);
        }

        // 代码随想录：
        // 有N件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。
        // 每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
        // dp[1][4]：有两种情况，放物品1还是不放物品1，
        // 如果不放物品1，那么背包的价值应该是dp[0][4]即容量为4的背包，只放物品0的情况
        // 如果放物品1，那么背包要先留出物品1的容量，目前容量为4，物品1的容量（就是物品1的重量）为3，此时背包剩下容量为1，容量为1，只考虑放物品0的最大价值是dp[0][1]，这个值我们之前计算过。
        // 所以放物品1的情况 =dp[0][1]+物品1的价值。
        // 两种情况，分别是放物品1 和 不放物品1，我们要取最大值（毕竟求的是最大价值）

        // 以上过程，抽象化如下：
        // 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i-1][j]
        // 放物品i：背包空出物品i的容量后，背包容量为j-weight[i],dp[i-1][j - weight[i]]为背包容量为j-weight[i]且不放物品i的最大价值，那么dp[i-1][j-weight[i]] + value[i](物品i的价值)，就是背包放物品i得到的最大价值。

        // 递推公式：dp[i][j] = max(dp[i-1][j]， dp[i-1][j - weight[i]] + value[i])
        public int knapsack1(int[] weight, int[] value, int bagWeight) {
            int[][] dp = new int[weight.length][bagWeight + 1];
            // 初始化
            for (int j = weight[0]; j <= bagWeight; j++) {
                dp[0][j] = value[0];
            }

            // weight数组的长度就是物品个数
            for (int i = 1; i < weight.length; i++) { // 遍历物品
                for (int j = 0; j <= bagWeight; j++) { // 遍历背包容量
                    if (j < weight[i]) {
                        dp[i][j] = dp[i - 1][j];
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
                    }
                }
            }
            return dp[weight.length - 1][bagWeight];
        }
        // 从二维数组转为一维数组（状态压缩）
        // 二维数组的dp[i][j]定义：表示从下表为[0-1]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
        // 一维数组的dp[j]定义：容量为j的背包，所背的物品价值最大为dp[j]。
        // 确定一维dp数组的递推公式：dp[j] = dp[j-weight[i]]+value[i],dp[j-weight[i]] 表示容量为j-weight[i]的背包所背物品的最大价值。
        // dp[j-weight[i]] + value[i]表示容量为j-物品i重量的背包加上物品i的价值（也就是容量为j的背包放入物品i之后的价值，即的dp[j]）
        // 此时有两个选择，一个是取dp[j]的值，另一个是取dp[j-weight[i]] + value[i]的值，这里一定是取最大的，毕竟是求最大价值。
        // 一维dp数组的遍历顺序：
        // 如果使用正序遍历：
        // dp[1] = dp[1-weight[0]] + value[0] = 15;
        // dp[2] = dp[2-weight[0]] + value[0] = 30;
        // 此时dp[2]就是30了，意味着物品0被放入了两次背包，所以不能使用正序遍历。
        // 为什么倒序遍历就可以保证物品只被放入一次背包呢？
        // 倒序遍历就是先计算dp[2]：
        // dp[2] = dp[2-weight[0]] + value[0] = 15;
        // dp[1] = dp[1-weight[0]] + value[0] = 15;
        // 所以从后往前遍历递推公式，每次取得的状态不会和之前取得的状态重合，这样每种物品就只会被取一次了。

        // 为什么二维dp数组中遍历背包的时候不用倒序呢？
        // 因为对于二维dp数组，dp[i][j]都是通过上一层即dp[i-1][j]计算而来的，本层的dp[i][j]并不会被覆盖。
        public int knapsack2(int[] weight, int[] value, int bagWeight) {
            int[] dp = new int[bagWeight + 1];
            dp[0] = 0;
            for (int i = 0; i < weight.length; i++) { // 遍历物品
                for (int j = bagWeight; i >= weight[i]; j--) { // 遍历背包容量
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
            return dp[bagWeight];
        }
    }

    // 416. 分割等和子集
    // 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
    // 一维dp数组
    static class CanPartition {
        public boolean canPartition(int[] nums) {
            if (nums == null || nums.length == 0) {
                return false;
            }
            int n = nums.length;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            // 总和为奇数，不能平分
            if (sum % 2 != 0) {
                return false;
            }
            int target = sum / 2;
            int[] dp = new int[target + 1];
            for (int i = 0; i < n; i++) {
                for (int j = target; j >= nums[i]; j--) {
                    // 物品i的重量是nums[i]，其价值也是nums[i]
                    dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
                }
                // 剪枝一下，每一次完成内层的for-loop,立即检查是否dp[target]
                if (dp[target] == target) {
                    return true;
                }
            }
            return dp[target] == target;
        }

        // 二维dp数组
        // 01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2.
        // 做完本题后，需要大家清晰：背包问题，不仅可以求背包能被背的最大价值，还可以求这个背包是否可以装满
        public boolean canPartition1(int[] nums) {
            int len = nums.length;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 2 != 0) {
                return false;
            }
            int target = sum / 2; //目标背包容量
            // 创建二维状态数组，行：物品索引，列：容量（包括 0）,这里的列是容量，不是价值
            /*
              dp[i][j]表示从数组的 [0, i] 这个子区间内挑选一些正整数
              每个数只能用一次，使得这些数的和恰好等于 j。
            */
            boolean[][] dp = new boolean[len][target + 1];
            // 先填表格第一行，第一个数只能让容积为它自己的背包恰好装满（这里的dp[][]数组的含义就是“恰好”，所以就算容积比它大的也不要）
            if (nums[0] <= target) {
                dp[0][nums[0]] = true;
            }
            // 再填表格后面几行
            // 外层遍历物品
            for(int i = 1; i < len; i++){
                // 内层遍历背包
                for(int j = 0; j <= target; j++){
                    // 直接从上一行先把结果抄下来，然后再修正
                    dp[i][j] = dp[i-1][j];
                    // 如果某个物品单独的重量恰好就等于背包的重量，那么也是满足dp数组的定义的
                    if (nums[i] == j){
                        dp[i][j] = true;
                        continue;
                    }
                    // 如果某个物品的重量小于j，那就可以看该物品是是否放入背包
                    // dp[i-1][j]表示该物品不放入背包，如果在[0, i-1]这个子区间内已经有一部分元素，使得它们的和为j，那么dp[i][j] = true;
                    // dp[i-1][i-nums[i]]表示该物品放入背包，如果在[0, i-1]这个子区间内就得找到一部分元素，使得它们的和为j-nums[i]。
                    if (nums[i] < j){
                        dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
                    }
                }
            }
            return dp[len-1][target];
        }
    }

    static class LengthOfLIS {
        // 1. 最长递增子序列（时间复杂度：O(N^2)）
        // dp[i]的值到底代表的是什么？
        // 我们的定义是这样的：dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度
        // 根据这个定义，我们就可以推出 base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。
        int lengthOfLIS(int[] nums) {
            int[] dp = new int[nums.length];
            // base case:dp数组全都初始化为1
            Arrays.fill(dp, 1);
            for (int i = 0; i < nums.length; i++) {
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) {
                        // 把 nums[i] 接在后面，即可形成长度为 dp[j] + 1，
                        // 且以 nums[i] 为结尾的递增子序列
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            int res = 0;
            // 要重新遍历一遍数组，找到最长的递增子序列长度
            for (int i = 0; i < dp.length; i++) {
                res = Math.max(res, dp[i]);
            }
            return res;
        }

        // 二分搜索（时间复杂度log(N)）
        int lengthOfLIS1(int[] nums) {
            int[] top = new int[nums.length];
            // 牌堆数初始化为0
            int piles = 0;
            for (int i = 0; i < nums.length; i++) {
                // 要处理的扑克牌
                int poker = nums[i];

                // ***** 搜索左侧边界的二分查找 *****
                int left = 0, right = piles;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (top[mid] > poker) {
                        right = mid;
                    } else if (top[mid] < poker) {
                        left = mid + 1;
                    } else if (top[mid] == poker) {
                        right = mid;
                    }
                }
                // ***********************************
                // 没找到合适的牌堆，新建一堆
                if (left == piles) {
                    piles++;
                }
                top[left] = poker;
            }
            // 牌堆数就是LIS长度
            return piles;
        }
    }

    static class MaxEnvelopes {
        // 力扣第 354 题「俄罗斯套娃信封问题」
        // 思路：先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序；之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度就是答案
        public int maxEnvelopes(int[][] envelopes) {
            int n = envelopes.length;
            // 按宽度升序排列，如果宽度一样，则按高度降序排列
            Arrays.sort(envelopes, (int[] a, int[] b) -> {
                return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
            });
            // 对高度数组寻找LIS
            int[] height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = envelopes[i][1];
            }
            // 调用lengthOfLIS会超时
            return lengthOfLIS1(height);
        }

        // 二分搜索（时间复杂度log(N)）
        int lengthOfLIS1(int[] nums) {
            int[] top = new int[nums.length];
            // 牌堆数初始化为0
            int piles = 0;
            for (int i = 0; i < nums.length; i++) {
                // 要处理的扑克牌
                int poker = nums[i];

                // ***** 搜索左侧边界的二分查找 *****
                int left = 0, right = piles;
                while (left < right) {
                    int mid = left + (right - left) / 2;
                    if (top[mid] > poker) {
                        right = mid;
                    } else if (top[mid] < poker) {
                        left = mid + 1;
                    } else if (top[mid] == poker) {
                        right = mid;
                    }
                }
                // ***********************************
                // 没找到合适的牌堆，新建一堆
                if (left == piles) {
                    piles++;
                }
                top[left] = poker;
            }
            // 牌堆数就是LIS长度
            return piles;
        }
    }

    static class MaxSubArray {
        // 最大子数组问题
        // 以nums[i]为结尾的“最大子数组和”为dp[i]
        // dp[i]有两种“选择”，要么与前面的相邻子数组链接，形成一个和更大的子数组；要么不与前面的子数组链接，自成一派，自己作为一个子数组
        int maxSubArray(int[] nums) {
            int n = nums.length;
            if (n == 0) {
                return 0;
            }
            int[] dp = new int[n];
            // base case
            // 第一个元素前面没有子数组
            dp[0] = nums[0];
            // 动态转移方程
            for (int i = 1; i < n; i++) {
                dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); // 这里主要是考虑了负数的情况
            }
            //得到nums的最大子数组
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++) {
                res = Math.max(res, dp[i]);
            }
            return res;
        }
    }
}
